from graph import Graph
from collections import deque
G = Graph((100,100), 10)
obstacle = [(2,2),(2,3),(2,4)]
G.set_obstacle(obstacle)


start_point = (0,0)
end_point = (G.m - 1, G.n - 1)
def get_neighbors(p):
    neighbors = []
    delta = [(0,1),(0,-1),(1,0),(-1,0)]
    for d in delta:
        x = p[0] + d[0]
        y = p[1] + d[1]
        if   (x >= 0 and x < G.m) and ( y >= 0 and y < G.n) and G.mat[x][y] == 1:
            # (x,y) is accessible and not out of graph
            neighbors.append((x, y))
    return neighbors
def BFS(start_point):
    Q = deque()
    visited = set()
    Q.append(start_point)
    visited.add(start_point)
    while len(Q)!= 0:
        V = Q.pop()
        print("current point",V)
        neighbors = get_neighbors(V)
        print("the neighbors: ", neighbors)
        print("Q:",Q)
        for neighbor in neighbors:
            if neighbor == end_point:
                print('*'*10,"arrived",'*'*10)
                return True
            if neighbor not in visited:
                visited.add(neighbor)
                G.mat[neighbor[0]][neighbor[1]] = -1
                Q.append(neighbor)
            
    
    return False

    
#print(get_neighbors((0,0)))
BFS(start_point)

print(G.mat)
